In currently-deployed navigation systems, the driver of a vehicle, such as a motor vehicle, can influence the route traveled in various ways, e.g., as described in published European patent document EP 0 979 987. For instance, the driver may select different optimizing criteria, such as “short route”, “fast route”, “avoid expressways” or the like, and/or can influence route sections, determined manually or using traffic telematics, which are then favored or avoided in the route calculation. The driver may also define one or more intermediate targets, which are then approached in sequence leading to a final target.
However, before searching for the route, the driver has to commit himself to an intermediate target which has to be a firm intermediate target. Thus, the intermediate targets or targets may essentially be divided into the following categories:                a road target given by one or more road sections that are connected to one another;.        road crossing target given by a target point which is established by the crossing of roads having different names;        directed point target or non-directed point target given by a target point which is mapped onto an orthopole on a nearby road section.        
However, the various target types mentioned above have in common that all the targets relate spatially to one enclosed region.
In some cases, there may be a desire on the part of the driver to be offered an optimum route to any one of several targets. For example, a driver may be looking for the nearest parking lot in a town that is unknown to him or may need a route to the nearest gas station, because his tank contents are low; alternatively, the route to the nearest branch of a fast food chain may be desired.
In the current navigation systems, the various applicable targets are shown in an index with a brief description. The user of the navigation system then can select one of these targets from the index and have a route determined. The index list in some conventional navigation systems, besides having a simple description, may also include a pertinent linear distance, and is sorted according to this linear distance.
In such cases, the nearest target from the current position can be very simply determined using the criterion of linear distance. However, in actual topography examples may be found in which these targets are not easy to reach from the current location of the means of locomotion, or rather, there are equivalent or even better alternative targets. Consequently, “nearest . . . ” does not necessarily mean the nearest target, but the target that is most easily reached.
In such current navigation system, the optimal target is ascertained by consecutive calculations of routes to all the targets offered in the index and by comparison of the same; this is a time-consuming and difficult process even when only the nearest three targets with regard to linear distances are to be considered.
After the user of a navigation system has decided on a target, then, this target is maintained. If it is not possible to follow the suggested route to the selected target, whether because of simply departing from the route and/or on account of road closings, the driver continues with the old target despite the fact that there may be a better target. This may lead to inefficient results. For example, it is possible that a route to a selected gas station may directly pass another possible gas station, which, at the start of the navigation, had seemed less favorable.
In order to implement a method according to the type described above a route network, such as a road network, is mapped by a digital map. According to an example implementation, a route-search algorithm according to Ford and Moore may be used. For this algorithm, the following criteria for imaging the route network may be used:
A route network, in particular a road network, can be depicted using a route-search algorithm as a graph having segments and having nodes. In this connection, the segments represent the routes and the nodes represent the interconnection points of the route network. Since in an actual road network traffic flow has direction, a segment is described with a vector having direction (See FIG. 1 which depicts an exemplary route network as a network of directed segments and of nodes situated between the directed segments).
Travel resistances or “segment resistances”, are allocated to the segments, where each segment resistance represents a measured variable for the effort of getting from one node in the network to another node in the network. In the simplest case, the length of the segment can be used directly as the segment resistance. Alternatively, making the assumption of an average traffic speed, the travel time on a segment may be regarded as its segment resistance; however, configurations are also conceivable in which travel time, length and other variables are linked with one another, in order to view the segment resistance of a map in a graph.
In addition, it may be noted at this point, that a resistance may also be allocated to the nodes.
All optimal path algorithms determine a route between a starting segment and a target segment in the directed graph having the property that the sum of all segment resistances allocated to the segments has a minimum. An algorithm for route calculation may build upon known optimal method algorithms according to Ford and Moore taken from graph theory; in this connection, these algorithms are adapted to the requirements for use in autonomous vehicle navigation systems.
The algorithm according to Ford and Moore is reverse-iterating, i.e., “visits” all the segments in the graph and evaluates the segments with respect to their favorable resistance to the target segment. This means, in other words, that, starting from a target segment, in each iterative step, the most favorable path is sought with respect to resistance, to the segments cited in a list and optimized in the previous iterative step. As a result, the method supplies the optimal route to the target segment from each segment in the graph.
To represent the calculation results, a route table is installed in the memory unit, which may appear as follows for an exemplary network according to FIG. 1:
Segment+Resistance+Successor−Resistance−Successork1∞−∞−k2∞−∞−k3∞−∞−k4∞−∞−k5∞−∞−k6∞−∞−k7∞−∞−k8∞−∞−k9∞−∞−
For each segment k1 through k9 in the graph, in this table, the resistance up to the target segment and the successor segment (=“successor”) in the target direction is stated. As an initial value, the resistance is set to “infinity” (∞) and the successor segment is set to “indefinite” (−), that is, the successor is deleted; a positive sign (“+”) in the resistance column and the successor column stands for viewing the segment in its arrow direction, and a negative sign (“−”) stands for viewing the segment counter to its arrow direction.
Before the start of the iterative optimization, the target segment in the above route table is initially given a resistance value of “zero”; in addition, the target segment is entered in the list of the already optimized segments, denoted as “first list” below. A “second list” is used for storing the segments to be tested in the next optimization step; at the beginning of the iterative optimization, the second list is empty.
After the initiation, the optimization method may begin. The segments shown in the first list are regarded as being the “actual” position of the vehicle, and all the segments interconnected with this actual segment, the so-called “arriver segments”, are submitted to an optimization test (designated by an O below). This yields the scenario illustrated in FIG. 2.
It is now assumed for the purposes of optimization that the vehicle is located on one of arriver segments, having a travel direction towards the actual segment. It is then tested as optimization condition whether the previous available route of the arriver segment is worse than the new route while using the actual segment; if the route via the actual segment proves to be better, an optimization is carried out. Corresponding to the configuration shown in FIG. 2, the following optimization relationships are derived:
OptimizationActual SegmentArriver SegmentO1a+k1−k1O1b+k1+k2O1c+k1−k3
For each actual arriver relationship according to the above table, there takes place the optimization testing which is shown by the example of arriver segment +k2 (→optimization O1b; see FIG. 2). In the optimization testing, the previous route table resistance of the arriver segment +k2 to the target is compared to the resistance which the arriver segment would have if it led to the target via the actual segment.
Optimization takes place if the so-called (resistance) optimization conditionRRT,actual(+k1)+Rsegment,Ank(+k2)<RRT(Alt),Ank(+k2) is satisfied,where RRT,actual(+k1)=resistance (from route table RT) of actual segment +k1 to the target;                Rsegment,Ank(+k2)=segment resistance of arriver segment +k2;        RRT(Alt),Ak(+k2)=resistance (from route table RT) of arriver segment +k2 to the target.        
The above optimization condition thus means, in other words, that the new resistance of the arriver segment is less than the previous resistance of the arriver segment. The resistance of the arriver segment is then replaced by the new, lower value in the route table, the actual segment is entered as the successor segment, and the optimized arriver segment is taken up into the second list.
If, in this manner, all the segments from the first list have been processed, the first list and the second list are exchanged; this means that the starting point for the next optimization is the segments optimized in the last method step. The method is ended when the first list is found to be empty, that is, when there are no longer any segments optimized in the previous pass.
We shall now explain the problem of a suboptimal route to the next target, in the light of an example:
The exemplary network to be considered is shown in FIG. 1. The assumption is made that segments k1, k3, k4, k6 as well as k9 each have the resistance value 10, and segments k2, k5, k7 as well as k8 each have the resistance value 20. At the time of consideration, the vehicle is located on segment +k8, i.e. the travel direction corresponds to the preferential direction.
The driver of the vehicle, starting from his actual position, would now like to have calculated for him the optimal route to a target of a certain category (this could be, for example, the first post office that comes along, or the first gas station, when the tank reserve of gasoline has already been activated). For this the driver of the vehicle calls up the index of the corresponding category (post offices, gas stations, . . . ) and receives the following list of the particular targets of that category that are located close to the actual position of the vehicle:
>20target A30target B
This list does not indicate which of the two targets A or B the better route is derived; on this matter, the linear distance between the actual position of the vehicle and individual targets, contained in the index list does not indicate this either. In the exemplary network of FIG. 1, target A is mapped on segment k1 and target B is mapped on segment k4, as may be seen in FIG. 3 in the light of a double arrow, one in each case.
On the basis of the above list, an initial preference would be for target A which is closer to the actual position of the vehicle. By applying the best path algorithm according to Ford and Moore, as well as by applying the corresponding optimization condition with respect to the resistance, there is derived, as shown in FIG. 4, the route to target A marked by the direction of the arrow, the overall resistance of the route to target A being exactly 50 units.
When determining the route from the actual position of the vehicle to target B, that lies at a greater distance from it, the actual difficulty becomes clear because, for this target B, the route shown in FIG. 5, marked by the direction of the arrows, has a total resistance of 40.
When comparing the two routes to target A and to target B, it becomes clear that the route to the nearest-lying target A does not produce the optimal route; the optimal route, in this example, is to the second-nearest target B. It is particularly a problem, in this connection, that the question as to which target produces the optimal route can be determined, using the conventional methods, only by successive calculations of the routes to all targets.